package com.fps.webshop.question.question0100_0199;

import java.util.HashSet;
import java.util.Set;

/**
 * 141. 环形链表
 * 
 * 给定一个链表，判断链表中是否有环。
 * 
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
 * 
 * 如果链表中存在环，则返回 true 。 否则，返回 false 。
 * 
 * 进阶：
 * 你能用 O(1)（即，常量）内存解决此问题吗？
 * 
 * 示例 1：
 * Question141_01.png
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：true
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 * 
 * 示例 2：
 * Question141_02.png
 * 输入：head = [1,2], pos = 0
 * 输出：true
 * 解释：链表中有一个环，其尾部连接到第一个节点。
 * 
 * 示例 3：
 * Question141_03.png
 * 输入：head = [1], pos = -1
 * 输出：false
 * 解释：链表中没有环。
 * 
 * 提示：
 * 		链表中节点的数目范围是 [0, 10^4]
 * 		-10^5 <= Node.val <= 10^5
 * 		pos 为 -1 或者链表中的一个 有效索引 。
 * 
 */
public class Question141 {
	
	class ListNode {
		int val;
		ListNode next;
		ListNode(int x) {
			val = x;
			next = null;
		}
	}
	 
	
	/**
	 * 第一次提交，尝试将每一个元素摘除，只保留head
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		1 ms	39.4 MB	Java	2021/08/16 16:48
	 * 
	 * 执行用时：1 ms, 在所有 Java 提交中击败了25.91%的用户
	 * 内存消耗：39.4 MB, 在所有 Java 提交中击败了62.47%的用户
	 */
	public static boolean hasCycle1(ListNode head) {
		if(head==null||head.next==null) {
			return false;
		}
		while(head.next!=null&&head.next!=head) {
			ListNode s = head.next.next;
			head.next.next = head;
			head.next = s;
		}
		if(head.next==null) {
			return false;
		}else {
			return true;
		}
		
    }
	
	/**
	 * 第二次提交，参考官方，使用HashSet进行判断
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		4 ms	39.1 MB	Java	2021/08/16 17:11
	 * 
	 * 执行用时：4 ms, 在所有 Java 提交中击败了20.08%的用户
	 * 内存消耗：39.1 MB, 在所有 Java 提交中击败了83.31%的用户
	 */
	public boolean hasCycle2(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while (head != null) {
            if (!seen.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }
	
	/**
	 * 第三次提交，参考官方，快慢双指针进行判断
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		0 ms	39.6 MB	Java	2021/08/16 17:13
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：39.6 MB, 在所有 Java 提交中击败了36.31%的用户
	 */
	public boolean hasCycle3(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

	/**
	 * 第四次提交，参考网友，优化快慢双指针，代码更简洁，但空间的开销反而增大了
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		0 ms	39.8 MB	Java	2021/08/16 17:14
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：39.8 MB, 在所有 Java 提交中击败了8.33%的用户
	 */
	public boolean hasCycle43(ListNode head) {
        ListNode s = head, f = head;
        while(f != null && f.next != null){ 
            s = s.next;
            f = f.next.next;
            if(s == f) return true;
        }
        return false;
    }
	
	public static void main(String[] args) {
		ListNode head = null;
		System.out.print(hasCycle1(head));
	}
}
